package LeetCode刷题;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-18 15:51
 * @description: Functions of this class is
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 **/
public class NoNo无重复字符的最长子串 {
    /**
     * 更快的解法（！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！）
     * class Solution {
     *     public int lengthOfLongestSubstring(String s) {
     *         int n = s.length();
     *         if (n <= 1) return n;
     *         int maxLen = 1;
     *
     *         int left = 0, right = 0;
     *         int[] window = new int[128];
     *         while (right < n) {
     *             char rightChar = s.charAt(right);
     *             int rightCharIndex = window[rightChar];
     *             left = Math.max(left, rightCharIndex);
     *             maxLen = Math.max(maxLen, right - left + 1);
     *             window[rightChar] = right + 1;
     *             right++;
     *         }
     *
     *         return maxLen;
     *     }
     * }
     *
     *
     *用“滑动窗口”方法解题：
     * 如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！
     * 我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着「枚举子串的起始位置」，而右指针即为上文中的
     * 在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；
     *
     * 在枚举结束后，我们找到的最长的子串的长度即为答案。
     *
     * 代码：
     * class Solution {
     *     public int lengthOfLongestSubstring(String s) {
     *         // 哈希集合，记录每个字符是否出现过
     *         Set<Character> occ = new HashSet<Character>();
     *         int n = s.length();
     *         // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
     *         int rk = -1, ans = 0;
     *         for (int i = 0; i < n; ++i) {
     *             if (i != 0) {
     *                 // 左指针向右移动一格，移除一个字符
     *                 occ.remove(s.charAt(i - 1));！！！！！！！！！！！！！这里不能放下标，要放那个字符！！！！！！！！
     *             }
     *             while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
     *                 // 不断地移动右指针
     *                 occ.add(s.charAt(rk + 1));
     *                 ++rk;
     *             }
     *             // 第 i 到 rk 个字符是一个极长的无重复字符子串
     *             ans = Math.max(ans, rk - i + 1);
     *         }
     *         return ans;
     *     }
     * }
     */
    public static void main(String args[]){
        System.out.println(lengthOfLongestSubstring("abcabcbb"));
    }
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set=new HashSet<>();
        int ans=0;
        int right=0;
        for(int i=0;i<s.length();i++){
            if(i!=0){
                set.remove(s.charAt(i-1));//如果i往前走了，即左指针更换了，就要把上一个左指针元素移除
            }
            while (right<s.length()&&!set.contains(s.charAt(right))){//开始判断右指针，如果右指针在边界内，同时右指针所指向的元素和之前的没有重复的话
                set.add(s.charAt(right));
                right++;//右指针向前移动
            }
            ans=Math.max(ans,right-i);//在左指针每次移动的时候，判断当前窗口内的内存是否要比之前的大
        }
        return ans;
    }
}